package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC451 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public String frequencySort(String str) {
            if (null == str || str.length() <= 0) return str;
            Map<Character, Integer> map = new HashMap<>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (map.containsKey(ch)) map.put(ch, map.get(ch) + 1);
                else map.put(ch, 1);
            }

            TreeMap<Integer, List<Character>> countMap = new TreeMap<>();
            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                int count = entry.getValue();
                char ch = entry.getKey();
                if (countMap.containsKey(count)) countMap.get(count).add(ch);
                else {
                    List<Character> list = new ArrayList<>();
                    list.add(ch);
                    countMap.put(count, list);
                }
            }


            for (Integer count : countMap.descendingKeySet()) {
                for (Character character : countMap.get(count)) {
                    for (int i = 0; i < count; i++) {
                        sb.append(String.valueOf(character));
                    }
                }
            }

            return sb.toString();
        }
    }

    public void run() {
        Solution solution = new Solution();
        //Input:
//"tree"
//
//Output:
//"eert"
        System.out.println(solution.frequencySort("tree"));
    }

    public static void main(String[] args) throws Exception {
        LC451 an = new LC451();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
